'''
二叉树
'''


class TreeNode(object):
    '''树节点'''

    def __init__(self, item):
        self.item = item
        self.l_child = None
        self.r_child = None


class Tree(object):
    '''二叉树'''

    def __init__(self, item=None):
        self.root = self.__get_tree_node(item)

    def __get_tree_node(self, o):
        if o is None:
            return None
        elif isinstance(o, TreeNode):
            return o
        else:
            return TreeNode(o)

    def add(self, item):
        '''添加元素'''
        node = self.__get_tree_node(item)
        if self.root is None:
            self.root = node
        else:
            queue = [self.root]
            while queue:  # 广度遍历
                current = queue.pop(0)
                if current.l_child is None:
                    current.l_child = node
                    return
                else:
                    queue.append(current.l_child)

                if current.r_child is None:
                    current.r_child = node
                    return
                else:
                    queue.append(current.r_child)

    def breadth(self):
        '''广度遍历,也叫层次遍历,按层次遍历'''
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            print(node.item, end=' ')
            if node.l_child:
                queue.append(node.l_child)
            if node.r_child:
                queue.append(node.r_child)

    '''深度优先:前序,中序,后序都属于中度遍历'''

    def pre_travel(self, node):
        '''前序遍历：根结点 ---> 左子树 ---> 右子树'''
        if node is None:
            return
        print(node.item, end=' ')
        self.pre_travel(node.l_child)
        self.pre_travel(node.r_child)

    def order_travel(self, node):
        '''中序遍历：左子树---> 根结点 ---> 右子树'''
        if node is None:
            return
        self.order_travel(node.l_child)
        print(node.item, end=' ')
        self.order_travel(node.r_child)

    def post_travel(self, node):
        '''后序遍历：左子树 ---> 右子树 ---> 根结点'''
        if node is None:
            return
        self.post_travel(node.l_child)
        print(node.item, end=' ')
        self.post_travel(node.r_child)


if __name__ == '__main__':
    tree = Tree()
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.breadth()
    print('\n前序:')
    tree.pre_travel(tree.root)
    print('\n中序:')
    tree.order_travel(tree.root)
    print('\n后序:')
    tree.post_travel(tree.root)
